#ifndef KDTREE
#define KDTREE

#include <iostream>
#include <vector>
#include "Photon.h"
#include <set>

using namespace std;



typedef struct{
    Photon * _ph;
    float dist;
} KDNode;

struct ClassKDTest {
  bool operator() (const KDNode& k1, const KDNode& k2) const
  {return k1.dist < k2.dist;}
};

class KDTree {
    public:
    KDTree(vector<Photon*> *&photons, int depth);
    float FindMedian();
    int _splitplane;
    vector<Photon*> FindClosestPhotons(Vector3, int, float);
    void FindKdTrees(Vector3 point, KDTree&, multiset<KDNode, ClassKDTest> &result, int N);
    private:
    Photon * _photon;
    KDTree *_left, *_right;
    vector<Photon*> * _internal;
    bool CreateNewTree();
    int _depth;
    float max_distance;
};


#endif



